/*
 * @Author       : wangzeyu 2309335887@qq.com
 * @Date         : 2023-06-30 10:55:18
 * @LastEditors  : WangZeYu
 * @LastEditTime : 2023-06-30 10:55:36
 * @FilePath     : \algorithm\bucketSort.js
 * @Description  : 桶排序(分治算法)
 */
let { insertSort } = require('./insertSort')
function bucketSort(arr, bucketSize = 3) {
  if (arr.length < 2) {
    return arr
  }
  const bucket = createBuncket(arr, bucketSize)
  console.log('bucket:', bucket)
  let result = []
  for (let i = 0; i < bucket.length; i++) {
    if (bucket[i].length > 0) {
      bucket[i] = insertSort(bucket[i])
      result.push(...bucket[i])
    }
  }
  return result
}

function createBuncket(arr, bucketSize) { // bucketSize决定了一个桶里有几种数;buncketCount:桶的数量
  let max = Math.max(...arr)
  let min = Math.min(...arr)
  let buncketCount = Math.floor((max - min) / bucketSize) + 1
  let bucket = [...Array(buncketCount)].map(() => [])
  for (let i = 0; i < arr.length; i++) {
    let index = Math.floor((arr[i] - min) / bucketSize)
    bucket[index].push(arr[i])
  }
  return bucket
}

console.log(insertSort)
let a = [1, 3, 5, 6, 9, 9, 15, 15, 3, 3, 8]

console.log(bucketSort(a))
